'''
两个单链表相交的一系列问题 【题目】 在本题中，单链表可能有环，也可能无环。给定两个 单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。
请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；如果不相交，返回null 即可。
要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)。
'''
class Node:
    def __init__(self, val: int):
        self.val = val
        self.next = None
def getIntersectNode(head1: Node, head2: Node) -> Node:
        if not head1 or not head2 : return None
        loop1 = getLoopNode(head1)  #得到第一个环
        loop2 = getLoopNode(head2)  #得到第二个环
        if not loop1 and not loop2 :  #两个链表是None，肯定没有环
            return noLoop(head1, head2)
        if loop1 and loop2 : 
            return bothLoop(head1, loop1, head2, loop2) #都有环
        return None
def getLoopNode(head: Node) -> Node:
    if not head or not head.next or not head.next.next: #少于三个节点，都没有环
        return None
    n1 = head.next # n1 -> slow
    n2 = head.next.next # n2 -> fast
    while n1 != n2:
        if not n2.next or not n2.next.next : #fast 不为空
            return None
        n2 = n2.next.next
        n1 = n1.next
    n2 = head       # n2 -> walk again from head 快指针放慢脚步
    while n1 != n2 :
        n1 = n1.next
        n2 = n2.next   
    return n1
def noLoop(head1: Node, head2: Node) -> Node:   #无环链表相交
    if not head1 or not head2:  return None
    cur1 = head1
    cur2 = head2
    n = 0
    while cur1.next : # cur 到达最后一个节点
        n += 1
        cur1 = cur1.next
    while cur2.next :
        n -= 1             #此时n就是两个链表的差值， n>0 说明head1 比较长
        cur2 = cur2.next
    if cur1 != cur2 : 
        print(cur1.val)
        return None # 不相交
    cur1 = head1 if n > 0 else head2  #cur1是较长的那个
    cur2 = head2 if cur1 == head1 else head1 #cur2是较短的那个
    n = abs(n)
    while (n != 0):
        n -= 1
        cur1 = cur1.next   #cur1是较长的， 先走n步
    while cur1 != cur2 :
        cur1 = cur1.next
        cur2 = cur2.next
    return cur1
def noLoop1(head1: Node, head2: Node) -> Node:  #无环链表相交, 时间复杂度太大了，但是常数时间也不长
        A, B = head1, head2
        while A != B:
            A = A.next if A else head2
            B = B.next if B else head1
        return A  

def bothLoop(head1: Node, loop1: Node, head2: Node, loop2: Node)-> Node:  #有环链表相交
        cur1 = cur2 = None
        if loop1 == loop2:   # 在环外相交
            cur1 = head1
            cur2 = head2
            n = 0
            while cur1 != loop1: #先走到入环口
                n += 1
                cur1 = cur1.next
            while cur2 != loop2: #先走到入环口
                n -= 1
                cur2 = cur2.next
            cur1 = head1 if n > 0 else head2  #cur1是较长的那个
            cur2 = head2 if cur1 == head1 else head1 #cur2是较短的那个
            n = abs(n)
            while n :
                n -= 1
                cur1 = cur1.next  #cur1是较长的那个,较长那个走多出来的几步
            while cur1 != cur2 :
                cur1 = cur1.next
                cur2 = cur2.next
            return cur1
        else :  # 在环上相交
            cur1 = loop1.next
            while cur1 != loop1 :
                if cur1 == loop2 : return loop1
                cur1 = cur1.next
            return None
def main():
    # 1->2->3->4->5->6->7->None
    head1 = Node(1)
    head1.next = Node(2)
    head1.next.next = Node(3)
    head1.next.next.next = Node(4)
    head1.next.next.next.next = Node(5)
    head1.next.next.next.next.next = Node(6)
    head1.next.next.next.next.next.next = Node(7)  
    # 0->9->8->6->7->None
    head2 = Node(0)
    head2.next = Node(9)
    head2.next.next = Node(8)
    head2.next.next.next = head1.next.next.next.next.next # 8->6
    print(getIntersectNode(head1, head2).val)   
    # 1->2->3->4->5->6->7->4...
    head1 = Node(1)
    head1.next = Node(2)
    head1.next.next = Node(3)
    head1.next.next.next = Node(4)
    head1.next.next.next.next = Node(5)
    head1.next.next.next.next.next = Node(6)
    head1.next.next.next.next.next.next = Node(7)
    head1.next.next.next.next.next.next = head1.next.next.next # 7->4 
    # 0->9->8->2...
    head2 =  Node(0)
    head2.next =  Node(9)
    head2.next.next =  Node(8)
    head2.next.next.next = head1.next # 8->2
    print(getIntersectNode(head1, head2).val)   
    # 0->9->8->6->4->5->6..
    head2 = Node(0)
    head2.next = Node(9)
    head2.next.next = Node(8)
    head2.next.next.next = head1.next.next.next.next.next # 8->6
    print(getIntersectNode(head1, head2).val)
if __name__ == '__main__' :
    main()


#面试题 02.07. 链表相交
#142. 环形链表 II